/*
 * tree.h
 *
 *  Created on: Apr 30, 2011
 *      Author: tqlong
 */

#ifndef TREE_H_
#define TREE_H_

#include <vector>

#define for_all_node_data(i) for (int i = 0; i < this->n(); i++)
#define for_all_node_child(i) for (int i = 0; i < this->n_child(); i++)

template<typename DERIVED,  typename DATA>
class Tree
{
public:
  //typedef Tree<DERIVED>                     self_type;
  typedef DERIVED                     derived_type;
  typedef DATA                        dataset_type;
  typedef typename DATA::vec_type     vec_type;
  typedef std::vector<int>            vint_type;
  typedef std::vector<derived_type*>  vtree_type;
public:
  Tree(dataset_type& data);
  Tree(Tree* p, int s, int e);
  virtual ~Tree();

  inline int n() const { return m_e-m_s; }
  inline int n_child() const { return m_child.size(); }
  inline int n_dim() const { return m_data.n_dim(); }

  inline int rootIdx(int idx) const { return m_s+idx; }
  inline int origIdx(int idx) const { return m_idx[m_s+idx]; }

  inline const vec_type& get(int i) const { return m_data.get(origIdx(i)); }
  inline double get(int i, int dim) const { return m_data.get(origIdx(i), dim); }

  inline derived_type* child(int i) const { return m_child[i]; }
  inline derived_type* self() { return static_cast<derived_type*>(this); }
  inline void swap(int i, int j) { int tmp = m_idx[m_s+i]; m_idx[m_s+i] = m_idx[m_s+j]; m_idx[m_s+j] = tmp; }

  void save(const std::string& fName);
  void saveTree(std::ostream& os);
  void load(const std::string& fName);
  void loadTree(std::istream& is);
protected:
//  virtual __Base* createChild(__Base* p, int s, int e) = 0; // every derived tree implement createChild()
protected:
  dataset_type& m_data;
  vint_type& m_idx;
  int m_s, m_e;
  derived_type *m_parent;
  vtree_type m_child;
};

/** Recursive search the tree with a visitor
  * Example: see kdtree.h for a knn visitor
  */

template <typename T, typename V>
double searchTree(T* t, V& v)
{
  // check bound
  if (!v.ok(t))
    return t->n();      // V implements bool v(T* t) : bounding box lower bound

  double pruned = 0;
  if (t->n_child() == 0) {
    int nn = t->n();
    for (int i = 0; i < nn; i++) {             // V implements bool v(T* t, i) : accept a point
      v.process(t, i);            // V implements void process(T* t, i) : process a point
      if (v.isDone()) break;      // V implements bool isDone() : termination condition
    }
  }
  else {
    int nc = t->n_child();
    for (int i = 0; i < nc; i++) {
      pruned += searchTree(t->child(i), v);   // recursive search on children
      if (v.isDone()) break;
    }
  }
  return pruned;
}

template<typename DERIVED, typename DATA>
Tree<DERIVED,DATA>::Tree(dataset_type& data) :
  m_data(data), m_idx(*new vint_type(data.n())),
  m_s(0), m_e(data.n()), m_parent(NULL)
{
  for (int i = 0; i < data.n(); i++) m_idx[i] = i;
}

template<typename DERIVED, typename DATA>
Tree<DERIVED,DATA>::Tree(Tree* p, int s, int e) :
  m_data(p->m_data), m_idx(p->m_idx), m_s(p->m_s+s), m_e(p->m_s+e), m_parent(static_cast<derived_type*>(p))
{
  p->m_child.push_back(self());
}

template<typename DERIVED, typename DATA>
Tree<DERIVED,DATA>::~Tree()
{
  if (!m_parent)
    delete &m_idx;
  for_all_node_child(i)
    delete m_child[i];
}

template<typename DERIVED, typename DATA>
void Tree<DERIVED,DATA>::save(const std::string& fName)
{
  std::ofstream os(fName.c_str());
  if (!os.good())
    {
//      Log::m_log << "Cannot open " << QString::fromStdString(fName) << endl;
      return;
    }

  os << this->n() << std::endl;
  for_all_node_data(i)
    os << this->m_idx[i] << " ";
  os << std::endl;

  this->saveTree(os);

  os.close();
}

template<typename DERIVED, typename DATA>
void Tree<DERIVED,DATA>::saveTree(std::ostream& os)
{
  os << this->m_s << " " << this->m_e << " " << this->n_child() << std::endl;
  for_all_node_child(i)
    child(i)->saveTree(os);
}

template<typename DERIVED, typename DATA>
void Tree<DERIVED,DATA>::load(const std::string& fName)
{
  std::ifstream is(fName.c_str());
  if (!is.good())
    {
      Log::m_log << "Cannot open " << QString::fromStdString(fName) << endl;
      return;
    }

  int nn;
  is >> nn;

  if (nn != this->n())
    {
      Log::m_log << "Number of points mismatch nn=" << nn << " n()=" << this->n() << endl;
      return;
    }

//  Log::m_log << nn << endl;
  for (int i = 0; i < nn; i++) is >> this->m_idx[i];
//  for (int i = 0; i < nn; i++) Log::m_log << this->m_idx[i] << " ";
//  Log::m_log << endl;
  this->loadTree(is);

  is.close();
}

template<typename DERIVED, typename DATA>
void Tree<DERIVED,DATA>::loadTree(std::istream& is)
{
  int nc;
  is >> this->m_s >> this->m_e >> nc;

//  Log::m_log << this->m_s << " " << this->m_e << " " << nc << endl;

  for (int i = 0; i < nc; i++) {
    derived_type *c = self()->createChild(self(), 0, 0);
    c->loadTree(is);
  }
}

#endif /* TREE_H_ */
